package com.leetcodehot.problems;

public class problems1658 {
    /**
     * 问题可以转化成 求最前面那段和最后面那段的数字总和刚好等于x 且 要求最短的数组
     * 难点在于如何同时两个部分进行？能否转化为一个来看待
     * 考虑了一下，最开始可以这样 先决定好前面那段最远能到哪？然后如果sum已经超过x则是不符合。
     * 每一次如果总和加起来刚好为x，那么就进行res最短的计算即可。
     * 前面的决定好了之后，就开始看后面那段 往左移，sum加完right后如果大于x说明left需要左移，否则则right继续左移
     */
    /**
     * 思考后决定以第一段为准第一段的左右称为left 和 right
     * 如果left<0 视为最后部分的n+left
     * 如果right==-1还不能停，可能需要继续left往左。
     */
    /**
     * 灵神还有个逆向思维的做法，巨聪明，改成从nums里面减去一段最长的连续子数组 使得 sum(nums)-sum(long)=x
     * 转为求long的长度即可
     * public int minOperations(int[] nums, int x) {
     *         int target = -x;
     *         for (int num : nums) target += num;
     *         if (target < 0) return -1; // 全部移除也无法满足要求
     *         int ans = -1, left = 0, sum = 0, n = nums.length;
     *         for (int right = 0; right < n; ++right) {
     *             sum += nums[right];
     *             while (sum > target) sum -= nums[left++]; // 缩小子数组长度
     *             if (sum == target) ans = Math.max(ans, right - left + 1);
     *         }
     *         return ans < 0 ? -1 : n - ans;
     *     }
     */
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int left = 0;
        int right = -1;
        int sum = 0;
        int res = Integer.MAX_VALUE;
        while (sum <= x && right < n - 1) {
            sum += nums[++right];
        }

        //如果所有数据sum都没到x 则返回-1
        if (right == n - 1 && sum < x) {
            return -1;
        }

        while (right>=0) {
            if (sum > x) {
                sum -= nums[right--];
            } else if (sum < x) {
                sum += nums[n + (--left)];
            } else {
                //sum==x
                res = Math.min(res, right+1-left);
                sum -= nums[right--];
            }
        }
        if(right == -1){
            while(sum<x){
                sum+=nums[n+(--left)];
            }
            if(sum == x){
                res = Math.min(res, right+1-left);
            }
        }
        if (res == Integer.MAX_VALUE) {
            return -1;
        }
        return res;
    }
}
